//
// Created by lucy on 1/18/2024.
//

#include "MutableLinkedContainer.h"

template <typename E>
LinkedNode<E> *MutableLinkedContainer<E>::getNodeAtIndex(int index)
{

    if (!this->validIndex(index))
    {
        printError();
        return nullptr;
    }

    LinkedNode<E> *temp = this->first;
    for (int i = 0; i < index; ++i)
    {
        temp = temp->next;
    }

    return temp;
}

template <typename E>
MutableLinkedContainer<E>::MutableLinkedContainer()
{
    first = nullptr;
    last = nullptr;
    len = 0;
}

template <typename E>
MutableLinkedContainer<E>::~MutableLinkedContainer()
{
    if (!first)
    {
        return;
    }
    LinkedNode<E> *p1 = first;
    LinkedNode<E> *p2 = first->next;

    while (p2 != nullptr)
    {
        delete p1;
        p1 = p2;
        p2 = p2->next;
    }

    delete p1;

    first = nullptr;
    last = nullptr;
    len = 0;
}

template <typename E>
bool MutableLinkedContainer<E>::validIndex(int index)
{
    if (index < 0 || index >= len)
    {
        return false;
    }
    else
    {
        return true;
    }
}

template <typename E>
void MutableLinkedContainer<E>::add(E ele)
{
    LinkedNode<E> *node = new LinkedNode<E>(ele);
    if (!len)
    {
        this->first = node;
        this->last = node;
    }
    else
    {
        this->last->next = node;
        node->pre = this->last;
        this->last = node;
    }
    len++;
}

template <typename E>
void MutableLinkedContainer<E>::add(int index, E ele)
{
    if (index < 0)
    {
        // printError();
        std::cerr << "Please enter index which is greater than 0" << std::endl;
        return;
    }

    LinkedNode<E> *node = new LinkedNode<E>(ele);
    if (!index)
    {
        node->next = this->first;
        this->first->pre = node;
        this->first = node;
        len++;
        return;
    }

    if (index >= len)
    {
        this->last->next = node;
        node->pre = this->last;
        this->last = node;
        len++;
        return;
    }

    int i = 0;
    LinkedNode<E> *temp = this->first;
    while (temp && i < len)
    {
        if (i == index - 1)
        {
            LinkedNode<E> *next = temp->next;
            temp->next = node;
            node->pre = temp;
            node->next = next;
            len++;
            return;
        }
        temp = temp->next;
        i++;
    }
}

template <typename E>
E MutableLinkedContainer<E>::remove(int index)
{

    /*
        if (!this->validIndex(index) || len == 0)
        {
            printError();
            return E{};
        }

        if (index == 0)
        {
            E e = this->first->ele;
            this->first = this->first->next;
            len--;
            return e;
        }
        E res{};
        int i = 0;
        LinkedNode<E> *temp = this->first;
        while (temp != nullptr && i < this->len)
        {
            if (i == index - 1)
            {
                res = temp->next->ele;
                // remove
                if (temp->next->next == nullptr)
                {
                    // 删除的是最后一个元素
                    delete temp->next;
                    temp->next = nullptr;
                    len--;
                }
                else
                {
                    LinkedNode<E> *next = temp->next->next;
                    delete temp->next;
                    temp->next = next;
                    next->pre = temp;
                    len--;
                }
            }
            temp = temp->next;
            i++;
        }

        return res;

        */

    if (!this->validIndex(index) || len == 0)
    {
        printError();
        return E{};
    }

    E res{};

    if (index == 0)
    {
        res = this->first->ele;
        this->first = this->first->next;
    }
    else
    {
        LinkedNode<E> *temp = getNodeAtIndex(index - 1);
        if (temp && temp->next)
        {
            res = temp->next->ele;
            LinkedNode<E> *next = temp->next->next;
            delete temp->next;
            temp->next = next;
            if (next)
                next->pre = temp;
        }
    }

    len--;
    return res;
}

template <typename E>
bool MutableLinkedContainer<E>::removeElement(E ele)
{
    int i = this->index(ele);

    if (i == -1)
    {
        return false;
    }
    this->remove(i);
    return true;
}

template <typename E>
void MutableLinkedContainer<E>::clear()
{
    if (!first)
    {
        return;
    }
    LinkedNode<E> *p1 = first;
    LinkedNode<E> *p2 = first->next;

    while (p2 != nullptr)
    {
        delete p1;
        p1 = p2;
        p2 = p2->next;
    }

    delete p1;

    first = nullptr;
    last = nullptr;
    len = 0;
}

template <typename E>
E MutableLinkedContainer<E>::set(int index, E ele)
{
    LinkedNode<E> *temp = getNodeAtIndex(index);
    if (!temp)
    {
        return E{};
    }
    E res = temp->ele;
    temp->ele = ele;
    return res;
}

template <typename E>
E MutableLinkedContainer<E>::get(int index)
{
    LinkedNode<E> *temp = getNodeAtIndex(index);
    if (!temp)
    {
        return E{};
    }
    return temp->ele;
}

template <typename E>
LinkedNode<E> *MutableLinkedContainer<E>::merge(LinkedNode<E> *left, LinkedNode<E> *right)
{
    LinkedNode<E> *result = nullptr;

    if (!left)
        return right;
    if (!right)
        return left;

    if (left->ele <= right->ele)
    {
        result = left;
        result->next = merge(left->next, right);
        result->next->pre = result;
    }
    else
    {
        result = right;
        result->next = merge(left, right->next);
        result->next->pre = result;
    }

    return result;
}

template <typename E>
LinkedNode<E> *MutableLinkedContainer<E>::mergeSort(LinkedNode<E> *head)
{
    if (!head || !head->next)
        return head;

    LinkedNode<E> *slow = head;
    LinkedNode<E> *fast = head->next;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    LinkedNode<E> *secondHalf = slow->next;
    slow->next = nullptr;

    LinkedNode<E> *left = mergeSort(head);
    LinkedNode<E> *right = mergeSort(secondHalf);

    return merge(left, right);
}

template <typename E>
void MutableLinkedContainer<E>::sort()
{
    this->first = mergeSort(this->first);

    // 更新最后一个节点
    LinkedNode<E> *temp = this->first;
    while (temp && temp->next)
    {
        temp = temp->next;
    }
    this->last = temp;
}

template <typename E>
int MutableLinkedContainer<E>::index(E ele)
{

    if (len == 0)
    {
        return -1;
    }
    LinkedNode<E> *temp = this->first;
    int i = 0;
    while (temp != nullptr)
    {
        if (ele == temp->ele)
        {
            return i;
        }
        temp = temp->next;
        i++;
    }
    return -1;
}

template <typename E>
std::string MutableLinkedContainer<E>::str()
{
    if (len == 0)
    {
        return "[]";
    }
    std::ostringstream oss;
    oss << "[";
    LinkedNode<E> *tmp = this->first;
    int l = 0;
    while (tmp != nullptr && l < len - 1)
    {
        oss << tmp->ele << ", ";
        l++;
        tmp = tmp->next;
    }

    oss << tmp->ele << "]";
    return oss.str();
}

template <typename E>
int MutableLinkedContainer<E>::length()
{
    return len;
}

template <typename E>
void MutableLinkedContainer<E>::printError()
{
    std::cerr
        << "Wrong! The index entered is incorrect (the index cannot be less than 0, and the index cannot be greater than "
        << len - 1 << ")" << std::endl;
}
